
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* p);

void STPush(ST* p, STDataType x);
void STPop(ST* p);

bool STEmpty(ST* p);

STDataType STTop(ST* p);

int STSize(ST* p);

void STDestroy(ST* p);

void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->top = 0;
	p->capacity = 0;
}

void STPush(ST* p, STDataType x)
{
	if (p->top == p->capacity)
	{
		int newsize = p->top == 0 ? 4 : p->capacity * 2;
		STDataType* newspace = (STDataType*)realloc(p->a, sizeof(STDataType) * newsize);
		if (newspace == NULL)
		{
			perror("realloc fail");
			return;
		}
		p->a = newspace;
		p->capacity = newsize;
	}
	p->a[p->top] = x;
	p->top++;
}

bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

void STPop(ST* p)
{
	assert(p);
	assert(!STEmpty(p));

	p->top--;
}

STDataType STTop(ST* p)
{
	assert(p);
	assert(!STEmpty(p));

	return p->a[p->top - 1];
}

int STSize(ST* p)
{
	assert(p);
	assert(!STEmpty(p));

	return p->top;
}

void STDestroy(ST* p)
{
	assert(p);

	free(p->a);
	p->a == NULL;
	p->capacity = p->top = 0;
}

typedef struct
{
	ST pushst;
	ST popst
} MyQueue;


MyQueue* myQueueCreate()
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	if (obj == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	STInit(&obj->pushst);
	STInit(&obj->popst);

	return obj;
}

void myQueuePush(MyQueue* obj, int x)
{
	STPush(&obj->pushst, x);
}

int myQueuePeek(MyQueue* obj)
{
	if (STEmpty(&obj->popst))
	{
		while (!STEmpty(&obj->pushst))
		{
			STPush(&obj->popst, STTop(&obj->pushst));
			STPop(&obj->pushst);
		}
	}
	return STTop(&obj->popst);
}

int myQueuePop(MyQueue* obj)
{
	int front = myQueuePeek(obj);
	STPop(&obj->popst);
	return front;
}

bool myQueueEmpty(MyQueue* obj) {
	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
	STDestroy(&obj->popst);
	STDestroy(&obj->pushst);
	free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/